package com.sicheng.蓝桥.练习题.基础数论;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/5 9:18
 */
public class 欧拉函数 {

    /**
     * 给定 n 个正整数 ai，请你求出每个数的欧拉函数。
     * <p>
     * <p>
     * 欧拉函数的定义
     * 1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
     * 若在算数基本定理中，N=p1^c1*p2^c2.....pm^cm，则：
     * ϕ(N) = N×(p1-1)/p1× (p2-1)/p2 ×...×(pm-1)/pm
     * 输入格式
     * 第一行包含整数 n。
     * <p>
     * 接下来 n 行，每行包含一个正整数 ai。
     * <p>
     * 输出格式
     * 输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
     * <p>
     * 数据范围
     * 1≤n≤100,
     * 1≤ai≤2×109
     * 输入样例：
     * 3
     * 3
     * 6
     * 8
     * 输出样例：
     * 2
     * 2
     * 4
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            int x = scanner.nextInt();
            int res = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    // ϕ(N) = N×(p1-1)/p1× (p2-1)/p2 ×...×(pm-1)/pm
                    // pi是x的因子
                    res = res / i * (i - 1);
                    while (x % i == 0) {
                        x /= i;
                    }
                }
            }
            if (x > 1) {
                res = res / x * (x - 1);
            }
            System.out.println(res);
        }

    }
}
